#include <iostream>
#include <queue>
#include "BinaryTree.h"

using namespace std;

class Solution
{
  public:
	vector<vector<int>> levelOrder(TreeNode *root)
	{
		vector<vector<int>> res;
		if (root == NULL)
			return res;
		queue<pair<TreeNode *, int>> q;
		q.push(make_pair(root, 0));
		while (!q.empty())
		{
			TreeNode *node = q.front().first;
			int level = q.front().second;
			q.pop();
			if (level == res.size())
				res.push_back(vector<int>());
			res[level].push_back(node->val);
			if (node->left)
				q.push(make_pair(node->left, level + 1));
			if (node->right)
				q.push(make_pair(node->right, level + 1));
		}
		return res;
	}
};

int main()
{
	int arr[] = {3, 9, 0, 0, 20, 15, 0, 0, 7, 0, 0};
	int n = sizeof(arr) / sizeof(arr[0]);
	TreeNode *tree = createBinaryTree(arr, n);
	preorderPrint(tree);
	cout << endl;
	vector<vector<int>> myVector = Solution().levelOrder(tree);
	for (int i = 0; i < myVector.size(); i++)
	{
		for (int j = 0; j < myVector[i].size(); j++)
		{
			cout << myVector[i][j] << " ";
		}
		cout << endl;
	}
	deleteBinaryTree(tree);
	return 0;
}
